﻿#define _CRT_SECURE_NO_WARNINGS 1

#include "SeqList.h"

//顺序表初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

//顺序表销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

void SLPrint(SL* ps)
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

//“增”的操作检查空间是否足够，不够就向内存申请空间
void CheckCapacity(SL* ps)
{
	//当有效数据个数size 与 有效空间大小capacity 相等时，说明空间不够了，要增容
	
	if (ps->capacity == ps->size)
	{
	    //增容，一般成倍增加，2~3倍较为合理
	    //用realloc函数，当ptr为空指针时，将分配一块新空间（调用realloc一样）
	    //此时又有一种特殊情况，一开始capacity为0时，怎样处理？
	    //三目操作符，为0时，将其赋值为4，不为0时，capacity*2
		int NewCapacity = (ps->capacity == 0 ? 4 : 2 * ps->capacity);
		SLDataType* tep = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));
		//判断增容成不成功
		if (tep == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tep;
		//及时更新空间大小
		ps->capacity = NewCapacity;
	}
}

//尾部插入
void SLPushBack(SL* ps, SLDataType x)
{
	//ps不能为空指针
	assert(ps);
	//空间是否足够
	CheckCapacity(ps);

	//尾插
	//ps->arr[ps->size] = x;
	//ps->size++;
	ps->arr[ps->size++] = x;
}

//头部插入
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	CheckCapacity(ps);

	//把全部数据整体往后移动一位，把第一位置空出来，再插入数据
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//循环的最后情况：ps->arr[1] = ps->arr[0]
	}

	//头插
	ps->arr[0] = x;
	ps->size++;
}

//尾部删除
void SLPopBack(SL* ps)
{
	assert(ps);
	//删除的前提是有数据，得判断有效数据个数size是否为0
	assert(ps->size);

	//尾删   
	//一种方法：ps->arr[--ps->size] = -1;
	//或者直接让size-1
	--ps->size;
}

//头部删除
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);

	//头删 把除第一位的数据整体往前移动一位，覆盖掉第一位的数据即可
	for (int i = 1; i < ps->size; i++)
	{
		ps->arr[i - 1] = ps->arr[i];//循环的最后情况：ps->arr[ps->size - 2] = ps->arr[ps->size - 1]
	}
	//及时更新size
	ps->size--;
}

//指定位置插⼊数据(不是覆盖原先数据，插入数据的结果造成部分数据后移) pos是下标
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//检查pos的有效性，pos是下标，不能为负的，pos最大只能为size
	assert(pos >= 0 && pos <= ps->size);
	CheckCapacity(ps);

	//指定位置插入， 先把pos位置的数据整体 往后 移一位（arr[pos] 至 arr[size - 1]），再插入
	for (int i = ps->size - 1; i >= pos; i--)
	{
		ps->arr[i + 1] = ps->arr[i];//循环的最后情况：ps->arr[pos + 1] = ps->arr[pos]
	}
	ps->arr[pos] = x;
	ps->size++;
}

//指定位置删除数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	//检查pos的有效性，pos是下标，不能为负的，pos最大只能为size - 1，为size就会越界
	assert(pos >= 0 && pos < ps->size);
	CheckCapacity(ps);

	//指定位置删除数据，让pos后面的数据往前移动（arr[pos+1] 至 arr[size -1]）,覆盖要删除的数据
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//循环的最后情况：ps->arr[size - 2] = ps->arr[size - 1]
	}
	ps->size--;
}

//查找整型指定数据
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	assert(ps->size);

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}